Spectral bandits for smooth graph functions with applications in recommender systems
基于图光滑函数的谱Bandit算法及其在推荐系统中的应用
🧭 图光滑Bandit · 有效维度 · 推荐冷启动 ★ 深度解读
Inria Lille · Microsoft Research · Technicolor Research Center
将图光滑性引入Bandit学习，通过有效维度使regret与节点数解耦，适用于探索阶段（T<N）的推荐场景
📌 工作参考价值（4 点）
- 物品冷启动探索：利用物品相似图（如内容/协同过滤构建的k-NN图）的拉普拉斯谱基，在用户反馈稀少时（T≪N），可以用少量试探发现高偏好物品，Regret远低于标准线性bandit。
- 有效维度作为复杂度指示：真实推荐场景中，物品图的有效维度d通常远小于总数N，可提前估算d来决定是否值得使用谱Bandit，若d接近T则普通LinUCB足够。
- SpectralTS实现高效探索：Thompson采样版本无需对每个物品计算置信区间，每次更新仅需O(N²)（V秩一更新+采样），比SpectralUCB的O(N³)更易于部署在大图上；适合需要毫秒级决策的在线推荐系统。
- 图光滑先验的注入方式：将图拉普拉斯作为正则项（谱惩罚）等价于假设物品奖励函数光滑，可复用到其他线性bandit或贝叶斯模型（如LinUCB/LinearTS）中，只需在协方差矩阵初始化时加入Λ=Λ_L+λI即可。